#include <iostream>
#include <vector>
using namespace std;

class QuickSort {
public:
  void quickSort(int a[], int left, int right) {
    // 在递归程序中一定要添加边界，当数组中元素个数大于1时才能进行递归操作
    if (left < right) {
      int pivot = partition(a, left, right);
      // 经过上面操作后，得到的 pivot 的位置已经可以确定，不需要改动
      quickSort(a, left, pivot - 1);
      quickSort(a, pivot + 1, right);
    }
  }

  /**
   * a[0]: 代表中枢点, 同时担任 "哨兵" 的任务
   * left: 左指针, 指向待排序序列的最左边
   * right: 右指针，指向待排序序列的最右边
   */
  int partition(int a[], int left, int right) {
    a[0] = a[left];
    while (left < right) {
      while (left < right && a[right] >= a[0])
        --right;
      a[left] = a[right];
      while (left < right && a[left] <= a[0])
        ++left;
      a[right] = a[left];
    }
    a[left] = a[0];
    return left;
  }
};

int main() {

  int a[100];
  for (int i = 1; i <= 100; i++) {
    a[i] = 100 - i;
  }
  QuickSort *qs = new QuickSort;
  qs->quickSort(a, 1, 100);
  for (auto &i : a) {
    cout << i << " ";
  }
  cout << endl;

  return 0;
}